from typing import *

from math import inf


class Solution:
    def minimumSum(self, grid: List[List[int]]) -> int:
        # 大思路：
        # A.横一刀，竖一刀，不切到底，左上切去一角，带有1的矩形，最小有多大？
        # B.经过A之后，第一种尝试，剩下横一刀，一切到底分成的两块，每块矩形最小有多大
        # C.经过A之后，第二种尝试，剩下竖一刀，一切到底分成的两块，每块矩形最小有多大
        # B,C 中有效的切法中最小的，同A组合成为三块

        # B，C横竖切法思路是一样的。
        # 以B，竖一刀为例，先把除去A块中的1，按照列收集每一列的最大最小
        # 然后从左到右切一次，从第一个有1的列开始是矩形左界，一直到当前每一个下刀位置，途中经过的每一列的最大最小，影响这个矩形的高度
        # 这期间，如果这一刀上没有1，那么左侧的矩形大小与前一刀相同
        # 同样的从右往左再切一次，目的是保证右侧和左侧都有有效的矩形
        # 竖切，横切思路一样，只不过一个是收集列信息，从左往右，从右往左
        # 一个是收集行信息，从上往下，从下往上
        m, n = len(grid), len(grid[0])

        ans = inf

        def p(r, c):  # 竖切，按列收集信息，一刀刀竖着切
            xmin = [m] * n  # 每一列的最小
            xmax = [0] * n  # 每一列的最大
            for i in range(m):
                for j in range(n):
                    if (i > r or j > c) and grid[i][j] == 1:  # 有效范围内
                        xmin[j] = min(xmin[j], i)
                        xmax[j] = max(xmax[j], i)
            f = [0] * n  # 从左往右竖着切，第i列和左侧，能产生的矩形面积
            u, d = m, 0
            l = n
            for i in range(n):
                if xmax[i] >= xmin[i]:
                    u = min(xmin[i], u)
                    d = max(xmax[i], d)
                    l = min(l, i)
                    f[i] = (i - l + 1) * (d - u + 1)
                else:
                    f[i] = f[i - 1] if i > 0 else 0
            ans = inf
            u, d = m, 0
            r = 0
            F = 0  # 从右往左竖着切，右侧能产生的矩形面积
            for i in range(n - 1, 0, -1):
                if xmax[i] >= xmin[i]:
                    u = min(xmin[i], u)
                    d = max(xmax[i], d)
                    r = max(r, i)
                    F = (r - i + 1) * (d - u + 1)
                if F > 0 and f[i - 1] > 0:  # 左右都有面积，左右都有1，才是两个有效矩形
                    ans = min(ans, F + f[i - 1])
            return ans

        def q(r, c):  # 横切
            xmin = [n] * m
            xmax = [0] * m
            for i in range(m):
                for j in range(n):
                    if (i > r or j > c) and grid[i][j] == 1:
                        xmin[i] = min(xmin[i], j)
                        xmax[i] = max(xmax[i], j)
            f = [0] * m
            u, d = n, 0
            l = m
            for i in range(m):
                if xmax[i] >= xmin[i]:
                    u = min(xmin[i], u)
                    d = max(xmax[i], d)
                    l = min(l, i)
                    f[i] = (i - l + 1) * (d - u + 1)
                else:
                    f[i] = f[i - 1] if i > 0 else 0
            ans = inf
            u, d = n, 0
            r = 0
            F = 0
            for i in range(m - 1, 0, -1):
                if xmax[i] >= xmin[i]:
                    u = min(xmin[i], u)
                    d = max(xmax[i], d)
                    r = max(r, i)
                    F = (r - i + 1) * (d - u + 1)
                if F > 0 and f[i - 1] > 0:
                    ans = min(ans, F + f[i - 1])
            return ans

        def k(x, y):  # 左上角，包含所有1的最小矩形面积I问题
            l, r, u, d = n, 0, m, 0
            for i in range(x + 1):
                for j in range(y + 1):
                    if grid[i][j] == 1:
                        l = min(l, j)
                        r = max(r, j)
                        u = min(u, i)
                        d = max(d, i)
            return (r - l + 1) * (d - u + 1) if r >= l else 0

        # A.横一刀i
        for i in range(m):
            for j in range(n):  # A.竖一刀j
                partA = k(i, j)  # 左上角，包含所有1的最小矩形面积I问题
                if partA > 0:  # 左上角有效
                    # p剩下的竖一刀，q是剩下的横一刀
                    ans = min(ans, partA + min(p(i, j), q(i, j)))
        return ans


s = Solution()
print(s.minimumSum([[1, 0, 1], [1, 1, 1]]))
print(s.minimumSum([[1, 0, 1, 0], [0, 1, 0, 1]]))
print(s.minimumSum([[0, 0, 0, 0], [1, 0, 1, 0], [1, 0, 0, 1]]))

# a = [0] * 10
# print(a)
# a[1] = 1
# print(a)

c = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [1, 0, 0, 1, 0, 0, 1, 0, 0, 0],
    [1, 1, 0, 0, 0, 0, 1, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
]
print(s.minimumSum(c))
大思路：
A.横一刀，竖一刀，不切到底，左上切去一角，带有1的矩形，最小有多大？
B.经过A之后，第一种尝试，剩下横一刀，一切到底分成的两块，每块矩形最小有多大
C.经过A之后，第二种尝试，剩下竖一刀，一切到底分成的两块，每块矩形最小有多大
B,C 中有效的切法中最小的，同A组合成为三块

B，C横竖切法思路是一样的。
以B，竖一刀为例，先把除去A块中的1，按照列收集每一列的最大最小
然后从左到右切一次，从第一个有1的列开始是矩形左界，一直到当前每一个下刀位置，途中经过的每一列的最大最小，影响这个矩形的高度
这期间，如果这一刀上没有1，那么左侧的矩形大小与前一刀相同
同样的从右往左再切一次，目的是保证右侧和左侧都有有效的矩形
竖切，横切思路一样，只不过一个是收集列信息，从左往右，从右往左
一个是收集行信息，从上往下，从下往上
